#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct BiTree
{
    ElemType data;
    struct BiTree *lchild;
    struct BiTree *rchild;
}BiTree,*Tree;
int Bst_insert(Tree &T,ElemType k) {
    Tree Treenew = (Tree) calloc(1, sizeof(BiTree));
    Treenew->data = k;
    if (T == NULL) {
        T = Treenew;
        return 1;
    }
    Tree p = T, parent;
    parent = p;
    while (p) {
        parent = p;
        if (k > p->data) {
            p = p->rchild;
        } else if (k < p->data) {
            p = p->lchild;
        } else {
            return 0;
        }
    }
    if (k > parent->data) {
        parent->rchild = Treenew;
    } else {
        parent->lchild = Treenew;
    }
    return 1;
}
void CreatTree(Tree &T,ElemType *str,int n)
{
    int i=0;
    while(i<n)
    {
    Bst_insert(T,str[i]);
    i++;
    }
}
void InOrder(Tree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        printf("%3d", T->data);
        InOrder(T->rchild);
    }
}
void DeleteTree(Tree &root,ElemType k)
{
    if (NULL==root)
    {
        return;
    }
    if (root->data>k)//当前结点的值大于要删除的结点，往左子树走
    {
        DeleteTree(root->lchild,k);
    }
    else if (root->data<k)//当前结点的值小于要删除的结点，往右子树走
    {
        DeleteTree(root->rchild,k);
    }
    else//找到要删除的结点
    {
        if (root->lchild==NULL)
        {
            Tree tempNode=root;
            root=root->rchild;
            free(tempNode);
        }
        else if(root->rchild==NULL)
        {
            Tree tempNode=root;
            root=root->lchild;
            free(tempNode);
        }
        else//两边都不为空
        {
            //一般删除的策略是左子树的最大数据或者右子树的最小数据，代替要删除的结点（这里采用左子树的最大数据）
            Tree tempNode=root->lchild;
            while(tempNode->rchild!=NULL)
            {
                tempNode=tempNode->rchild;
            }
            root->data=tempNode->data;
            DeleteTree(root->lchild,tempNode->data);
        }
    }
}
int main()
{
    Tree T=NULL;
    ElemType str[]={21,12,31,13,45,67,78};
    CreatTree(T,str,7);
    DeleteTree(T,12);
    InOrder(T);
}